home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Language/OS - Multiplatform Resource Library
/
LANGUAGE OS.iso
/
cpp_libs
/
cool
/
ge_cool.lha
/
GE_COOL2.1
/
src
/
Tree
/
Binary_Tree.C
< prev
next >
Wrap
C/C++ Source or Header
|
1992-06-29
|
14KB
|
369 lines
//
// Copyright (C) 1991 Texas Instruments Incorporated.
//
// Permission is granted to any individual or institution to use, copy, modify,
// and distribute this software, provided that this complete copyright and
// permission notice is maintained, intact, in all copies and supporting
// documentation.
//
// Texas Instruments Incorporated provides this software "as is" without
// express or implied warranty.
//
#include <cool/Binary_Tree.h>
// CoolBinary_Tree -- Simple constructor to initialize a CoolBinary_Tree object
// Input: None
// Output: None
template <class Type>
CoolBinary_Tree<Type>::CoolBinary_Tree<Type> () {
this->compare = &Type##_default_node_compare; // Pointer to compare function
}
// CoolBinary_Tree -- constructor to initialize a CoolBinary_Tree object to have the
// same size and values as some other CoolBinary_Tree object
// Input: Reference to CoolBinary_Tree
// Output: None
template <class Type>
CoolBinary_Tree<Type>::CoolBinary_Tree<Type> (const CoolBinary_Tree<Type>& b)
{
this->compare = b.compare; // Pointer to compare function
this->number_nodes = b.number_nodes;
this->root = this->copy_nodes (b.get_root());
this->current_position () = b.current_position ();
}
// ~CoolBinary_Tree -- Destructor for the CoolBinary_Tree class
// Input: None
// Output: None
template <class Type>
CoolBinary_Tree<Type>::~CoolBinary_Tree<Type> () {
delete this->root; // Virtual destructor called recurs.
} // on all nodes
// value -- Return value of node at current position
// Input: None
// Output: Reference to value of node at current position
template <class Type>
Type& CoolBinary_Tree<Type>::value () {
#if ERROR_CHECKING
if (this->state.stack.is_empty() ) // If invalid current position
this->curpos_error (#Type, "value()"); // Raise exception
#endif
Stack_Entry stack_entry = this->state.stack.top(); // get top stack
return (((CoolBinary_Node<Type>*)stack_entry.get_first())->get()); // Return value
}
template <class Type>
Boolean CoolBinary_Tree<Type>::put_internal
(const Type& value, Boolean avl) {
if (this->root == NULL) { // If this is the first node
this->root = new CoolBinary_Node<Type> (value); // Add new node and value
this->number_nodes++; // Update node count
return TRUE; // Indicate success
}
CoolBinary_Node<Type>* ptr = (CoolBinary_Node<Type>*)this->root; // Start at root
BT_Stack stack; // Stack for AVL balancing
while (TRUE) { // Until we find location
int pos = (*this->compare)(ptr->get(),value); // Compare data values
if (pos == 0) // If data value exists in tree
return FALSE; // indicate node not added
else if (pos > 0) { // Data down left subtree?
if (avl)
stack.push (Stack_Entry ((CoolBinary_Node*)ptr,LEFT)); // Push parent
if (ptr->get_ltree() == NULL) { // If at leaf node
ptr->set_ltree ((new CoolBinary_Node<Type> (value))); // Add node to ltree
this->number_nodes++; // Update node count
break; // Break out of loop and exit
}
else {
ptr = ptr->get_ltree(); // Else point to left subtree
continue; // And continue search
}
}
else { // Else down right subtree
if (avl)
stack.push (Stack_Entry ((CoolBinary_Node*)ptr,RIGHT)); // Push on stack
if (ptr->get_rtree() == NULL) { // If at leaf node
ptr->set_rtree ((new CoolBinary_Node<Type> (value))); // Add node to rtree
this->number_nodes++; // Update node count
break; // Break out of loop and exit
}
else {
ptr = ptr->get_rtree(); // Grab right subtree dir
continue; // And continue to search;
}
}
}
if (avl) // Balance it if an AVL tree
CoolBinary_Tree::avl_put_balance (stack);
this->reset(); // Invalidate current position
return TRUE; // Return success
}
// remove_internal -- does the actual work of removing a value from bin tree
// for avl trees, will make call to check avl balance
// Input: -- value to remove + optional Boolean for AVL trees
// output -- TRUE if item sucessfully removed. FALSE otherwise.
template <class Type>
Boolean CoolBinary_Tree<Type>::remove_internal
(const Type& value, Boolean avl) {
if (this->root == NULL) // If there are no nodes
return FALSE; // indicate failure
BT_Stack stack1; // Allocate traversal stack
Left_Right route = NONE; // Last subtree taken
CoolBinary_Node<Type> *ptr = (CoolBinary_Node<Type>*)this->root; // Start at root
CoolBinary_Node<Type> *parent_ptr = NULL; // Save pointer to parent
CoolBinary_Node<Type> *ptr1, *ptr2; // temp ptrs to nodes
while (TRUE) { // Until we find location
int pos = (*this->compare)(ptr->get(),value); // Compare data values
if (pos == 0) { // If node to delete is found
if (ptr->get_rtree() == NULL) { // If no right subtree
if (route == LEFT) // If child of parent's ltree
parent_ptr->set_ltree(ptr->get_ltree()); // Set to left subtree
else if (route == RIGHT)
parent_ptr->set_rtree(ptr->get_ltree()); // Set to right subtree
else this->root = ptr->get_ltree(); // Make ltree the new root
}
else if (ptr->get_ltree() == NULL) { // Else if no left subtree
if (route == LEFT) // If child of parent ltree
parent_ptr->set_ltree(ptr->get_rtree()); // Set to left subtree
else if (route == RIGHT)
parent_ptr->set_rtree(ptr->get_rtree()); // Set to right subtree
else this->root = ptr->get_rtree(); // rtree is the new root.
}
// Node(a) with value to be deleted has both a left and right subtree.
// We need to look for the node(b) with the next smallest value and
// copy it's value into node(a). Then adjust the parent of node(b)
// to point at node(b)'s left subtree (right subtree will always be
// NULL). ptr is left pointing at node(b) so it is the
// one which is eventually deleted.
else {
if (avl) // for avl trees
stack1.push (Stack_Entry((CoolBinary_Node*)ptr,LEFT)); // push on stack
ptr1 = ptr; // Save node with matched data
ptr2 = ptr1; // last parent initially ptr
ptr = ptr->get_ltree(); // Start with node's ltree
while (ptr->get_rtree() != NULL) { // Follow rtree til null rtree
if (avl) // for avl trees
stack1.push (Stack_Entry((CoolBinary_Node*)ptr,RIGHT)); // push on stack
ptr2 = ptr; // save last parent
ptr = ptr->get_rtree(); // get right subtree
}
ptr1->set (ptr->get()); // Move next smallest value up
if (ptr1 == ptr2) // ltree had no rtrees
ptr2->set_ltree (ptr->get_ltree()); // Del node is parents ltree
else
ptr2->set_rtree (ptr->get_ltree()); // Del node is parents rtree
}
// DELETE the node ptr points at
this->number_nodes--; // Decrement node count
if (this->number_nodes == 0) // If no more nodes in tree
this->root = NULL; // Nullify root pointer
ptr->set_ltree (NULL); // Nullify left subtree pointer
ptr->set_rtree (NULL); // Nullify right subtree pointer
delete ptr; // Deallocate memory
this->reset(); // Invalidate current position<
break; // exit loop
}
else if (pos > 0) { // Data down left subtree?
if (ptr->get_ltree() == NULL) { // If at leaf node
return FALSE; // Indicate node not found
}
else {
if (avl) // if avl tree
stack1.push (Stack_Entry((CoolBinary_Node*)ptr,LEFT)); // push on stack1
parent_ptr = ptr; // Save parent pointer
route = LEFT; // Save route taken
ptr = ptr->get_ltree(); // point to left subtree
continue; // And continue to search;
}
}
else { // Else down right subtree
if (ptr->get_rtree() == NULL) // If at leaf node
return FALSE; // Indicate success
else {
if (avl) // If an avl tree
stack1.push (Stack_Entry((CoolBinary_Node*)ptr,RIGHT)); // push on stack
parent_ptr = ptr; // Save parent pointer
route = RIGHT; // Save route taken
ptr = ptr->get_rtree(); // Point to right subtree
continue; // And continue to search;
}
}
}
// The node has been removed. Now every node in the path of the deleted
// node must be checked for possible re-balancing if this is an AVL tree
if (avl)
CoolBinary_Tree::avl_remove_balance (stack1);
return TRUE;
}
// find -- Find a value in the sorted binary tree
// Input: Reference to value to find
// Output: Current position updated and TRUE if item found, FALSE otherwise
template <class Type>
Boolean CoolBinary_Tree<Type>::find (const Type& value) {
for (this->reset (); this->next (); ) // For each node in the tree
if ((*this->compare)(this->value(), value) == 0) // If value found in cache
return TRUE; // Indicate item found
return FALSE; // Else indicate failure
}
// operator<< -- Output a binary tree by printing it sideways where the root is
// printed at the left margin. To obtain the normal orientation,
// rotate the output 90 degrees clockwise
// Input: Reference to output stream, reference to CoolBinary_Tree<Type>
// Output: Reference to output stream
template <class Type> CoolBinary_Tree {
ostream& operator<< (ostream& os, const CoolBinary_Tree<Type>& b) {
Type##_print_tree((CoolBinary_Node<Type>*)b.get_root(),os); // Print tree
return os; // Return output stream
}
}
template <class Type> CoolBinary_Tree {
void Type##_print_tree (const CoolBinary_Node<Type>* b, ostream& os) {
static indent = 0; // Temporary variables
if (b != NULL) { // If not at bottom of tree
indent += 1; // Indent node
Type##_print_tree (b->get_rtree(),os); // Output the right subtree
for (int i = 1; i < indent; i++) // For each level of tree
os << " "; // Indent some number of spaces
os << b->get() << "\n"; // Output node data value
Type##_print_tree (b->get_ltree(),os); // Output the left subtree
indent -= 1; // Decrement indent level
}
}}
// operator= -- Overload the assignment operator to copy a CoolBinary_Tree object
// to another Binary Tree object
// Input: Reference to CoolBinary_Tree
// Output: Reference to CoolBinary_Tree
template <class Type>
CoolBinary_Tree<Type>& CoolBinary_Tree<Type>::operator= (CoolBinary_Tree<Type>& b) {
delete this->root; // Delete old tree nodes, virtual
this->compare = b.compare; // Pointer to compare function
this->number_nodes = b.number_nodes;
this->current_position () = b.current_position ();
this->root = this->copy_nodes (b.get_root());
return *this; // Return tree reference
}
template <class Type>
inline CoolBinary_Node<Type>* CoolBinary_Tree<Type>::copy_nodes(const CoolBinary_Node<Type>* bn) const{
CoolBinary_Node<Type>* new_nodes = NULL;
if (bn)
new_nodes = bn->copy_nodes(bn);
return new_nodes;
}
// balance -- Build a perfectly balanced binary tree from the existing tree
// and delete old tree and storage. This uses the private recursive
// method baltree() to construct the left and then right subtrees.
// Input: None
// Output: None
template <class Type>
void CoolBinary_Tree<Type>::balance () {
CoolBinary_Node<Type>* p; // Temporary node pointer
if (this->number_nodes != 0) { // If there are nodes in tree
this->reset (); // Recalculate node cache
p = this->baltree (this->number_nodes); // Generate balanced tree
delete this->root; // Delete old tree, virtual
this->root = p; // Point to new balanced tree
}
}
template <class Type>
CoolBinary_Node<Type>* CoolBinary_Tree<Type>::baltree (long n) {
long nleft, nright; // Number nodes in ltree,rtree
CoolBinary_Node<Type>* p; // Temporary pointer
if (n == 0) // If no more nodes left
return NULL; // Return NULL pointer
nleft = n >> 1; // Node count for left subtree
nright = n - nleft - 1; // Node count for right subtree
p = new CoolBinary_Node<Type> (); // Allocate new node
p->set_ltree(this->baltree (nleft)); // Create left subtree
p->set ((this->next(), this->value())); // Set node value
p->set_rtree(this->baltree (nright)); // Create right subtree
return p; // Return pointer to subtree
}
// operator== -- Compare binary trees for same values and structure
// Input: constant reference to another binary tree
// Output: TRUE/FALSE
template <class Type>
Boolean CoolBinary_Tree<Type>::operator== (CoolBinary_Tree<Type>& t) {
Boolean t1, t2;
for (this->reset(), t.reset(); // Start at first node of each
(t1 = this->next()) && (t2 = t.next());) // For each node in tree
if ((*this->compare)(this->value(), t.value()) != 0) // If different value
return FALSE; // Trees not equal
if (t1 == FALSE) // If no more nodes
if (t.next () == FALSE) // in either tree
return TRUE; // Trees are equal
else
return FALSE;
return FALSE; // Else not equal
}
// set_compare -- Specify the comparison function to be used in logical tests
// of node data values
// Input: Pointer to a compare function
// Output: None
template <class Type>
void CoolBinary_Tree<Type>::set_compare (Type##_Tree_Compare cf) {
if (cf) // If compare function given
this->compare = cf; // Set pointer
else
this->compare = &Type##_default_node_compare; // Pointer to default compare
}
// default_node_compare -- Default node comparison function utilizing builtin
// less than, equal, and greater than operators
// Input: Reference to two Type data values
// Output: -1, 0, or 1 if less than, equal to, or greater than
template <class Type> CoolBinary_Tree {
int Type##_default_node_compare (const Type& v1, const Type& v2) {
if (v1 == v2) // If data items equal
return 0; // Return zero
if (v1 < v2) // If this less than data
return -1; // Return negative one
return 1; // Else return positive one
}
}